/*
Given a string s and a dictionary of words dict, determine if s can be
segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".
*/

class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
    	set<int> segable_seg_start_indexs,not_segable_seg_start_indexs;
    	return wordBreakHelper(s, dict,segable_seg_start_indexs,not_segable_seg_start_indexs);
    }

   
private:
   //Dynamic programming, namely recursion + memorization
   //We should memorize the which suffix in both can or can not segmentable situations.  
    bool wordBreakHelper(string s, unordered_set<string> &dict,set<int> &segable_seg_start_indexs, set<int> &not_segable_seg_start_indexs)
    {
    	if(segable_seg_start_indexs.find(s.length()) != segable_seg_start_indexs.end())
    		return true; //Find it in segmentable cache
    	if(dict.find(s) != dict.end() ) //not find in cache, but in dict
    	{
    		segable_seg_start_indexs.insert(s.length());
    		return true;
    	}
    	for(uint i=1; i<s.length();i++)
    	{
    		if(dict.find(s.substr(0,i)) != dict.end()){ //If start part can be find in dict
    			if(segable_seg_start_indexs.find(s.length()-i) != segable_seg_start_indexs.end())return true; //Find in segmentable cache
    			if(not_segable_seg_start_indexs.find(s.length()-i) != not_segable_seg_start_indexs.end()) continue;
    			if(wordBreakHelper(s.substr(i,s.length()-i),dict,segable_seg_start_indexs,not_segable_seg_start_indexs))
    			{
    				    segable_seg_start_indexs.insert(s.length()-i);
    					return true;
    			}
    			else{
    				not_segable_seg_start_indexs.insert(s.length()-i);
    			}
    		}
    	}

    	//after try all and not segmentable, then return false
    	return false;
    }
};